In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
We wsi Bajtowo wszystkie gospodarstwa są położone po jednej stronie bardzo długiej drogi, gdyż po jej drugiej stronie znajduje się Bajtocki Park Narodowy i tam gospodarstw budować nie wolno. Wójt wsi postanowił wpłynąć pozytywnie na jej rozwój (a co za tym idzie na zawartość swojego portfela) i przekształcić ją w potentata branży meblowej. Dlatego też wybudowano tyle samo tartaków co gospodarstw we wsi, wszystkie oczywiście przy jedynej we wsi drodze. Wójt postanowił, że każdy tartak będzie dostarczał drewno jednemu, ściśle dla niego określonemu gospodarstwu, które będzie produkować z tego drewna meble.
Wójt natrafił jednak na problem natury logistycznej - brakowało możliwości transportu drewna, gdyż jedyna wiejska droga była zbyt ruchliwa i niebezpieczna. Dlatego też postanowił wybudować drogi, które będą łączyły tartaki z gospodarstwami (jeden tartak ma być połaczony z jednym gospodarstwem). Drogi te ze względów bezpieczeństwa nie mogą się przecinać; ponadto mogą one przebiegać wyłącznie po jednej stronie głównej wiejskiej drogi, nie mogą wkraczać na teren parku narodowego.
Ponieważ wójt ma problemy z takim połączeniem tartaków z gospodarstwami w pary, aby dało się żądany układ dróg wytyczyć, poszukuje informatyka, który mu w tym pomoże (a już wkrótce będzie go mógł sowicie wynagrodzić!). Czy skusisz się i pomożesz wójtowi?
Napisz program który:
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę gospodarstw we wsi. Drugi wiersz zawiera jeden napis o długości , złożony wyłącznie z liter g i t, oznaczający układ gospodarstw i tartaków przy drodze. Droga biegnie w kierunku wschód-zachód, układ gospodarstw i tartaków podany jest w kierunku z zachodu na wschód, a park położony jest na południe od drogi (patrz też rysunek przykładowy).
Jeśli szukane przyporządkowanie nie istnieje, Twój program powinien wypisać na standardowe wyjście jedno słowo . W przeciwnym razie powinien wypisać wierszy. Każdy z nich powinien zawierać parę liczb całkowitych, oddzielonych pojedynczym odstępem i oznaczających numer gospodarstwa i numer tartaku, które powinny być połączone drogą. Gospodarstwa numerujemy w kierunku z zachodu na wschód liczbami od do (tartaki podobnie; gospodarstwa i tartaki mają oddzielną numerację). Jeżeli istnieje więcej niż jedno poprawne przyporządkowanie, Twój program powinien wypisać dowolne z nich.
3 gtggttpoprawną odpowiedzią jest:
2 1 1 3 3 2
Przykładowe połączenie gospodarstw (czarne kółka) i tartaków (białe kółka)
drogami.
Uwaga: Istnienie ,,odstępów'' między gospodarstwami i tartakami a główną drogą służy tylko lepszemu zilustrowaniu sytuacji - w rzeczywistości gospodarstwa i tartaki leżą tuż przy drodze i nie można prowadzić drogi między którymkolwiek gospodarstwem czy tartakiem a główną drogą.
Autor zadania: Jakub Radoszewski.